ERRATA LIST for BOOK:
Fundamental Problems in Algorithmic Algebra
THIS LIST IS POSTED at /http://cs.nyu.edu/yap/book/
PLEASE CONTACT THE AUTHOR AT yap@cs.nyu.edu
===============================================================================
page line BUG REPORT [RESPONSE] name date
===============================================================================
---- FRONTISPIECE MATERIAL ----------------------------------------------------
vii chap.2 & 2.4 Denominator => Divisor Buell 6/1/00
xiii para.2, l.4 \'a => \`a Chazelle 1/21/00
-5 leit motif => leitmotif Fateman 2/17/00
-3 elemination => elimination Chazelle 1/21/00
-2 Contiuned => Continued Chazelle 1/21/00
xv 7 Algebrea => Algebra Koegl 1/18/00
10 Birkäuser => Birkhäuser Koegl 1/18/00
16 Spring-Verlag => Springer-Verlag Koegl 1/18/00
-7 Algebriac => Algebraic Koegl 1/18/00
-7 Coputing => Computing Koegl 1/19/00
-2 Compoutation => Computation Koegl 1/18/00
-0 Various people have pointed out additional
books that ought to belong to my list.
MORE TEXTBOOKS:
E. Bach, J. Shallit:
Algorithmic Number Theory -
Volume 1, Efficient Algorithms,
MIT Press, Cambridge, Mass., 1996.
M. Bronstein:
Symbolic Integration I - Transcendental Functions,
Springer-Verlag, Berlin, 1997.
P. Bürgisser, M. Clausen, M. A. Shokrollahi:
Algebraic Complexity Theory,
Springer-Verlag, Berlin, 1997.
J. von zur Gathen, J. Gerhard:
Modern Computer Algebra,
Cambridge University Press, 1999.
M. Pohst, H. Zassenhaus:
Algorithmic Algebraic Number Theory,
Cambridge University Press, 1997.
M. Mignotte, D. Stefanescu:
Polynomials - An Algorithmic Approach
Springer-Verlag, Singapore, 1999.
W. V. Vasconcelos:
Computational Methods in Commutative Algebra
and Algebraic Geometry,
Springer-Verlag, Berlin, 1998.
F. Winkler:
Polynomial Algorithms in Computer Algebra,
Springer-Verlag, Wien, 1996.
---- CHAP 0: INTRODUCTION -----------------------------------------------------
1 2nd citation D'Alembart => d'Alembert Koegl 1/19/00
2 4, 6 lead(P): "lead" should have \tt font Buell 6/1/00
7 2 of (0.9) Add a '.' at the end. Koegl 1/19/00
9 15f. How should the '+ 1' account for a
"separator between the two integers"?
I do not see how a single bit could
help to distinguish between the numerator
and the denominator.
Koegl 1/19/00
[FIX: I NEED log(p) additional bits,
not constant]
19f. Same discussion applies here. For a more
detailed account of space requirements one
would have to discuss implementation
issues more deeply.
Koegl 1/19/00
[FIX: AGAIN, I NEED
"+log(size(a_{ij}))" bits]
-9 I feel that you have an unfair
characterization that sparse representation
increase the computational complexity
of problems. Fateman 2/18/00
[FIX: Technically, I am correct, but the
negative connotation is unwarranted!
Please insert the following sentences:
"This does not mean that the sparse
representation is undesirable. Indeed, in
practice, it is often the only feasible
representation. Basically these complexity
results say that the sparse representation
can be super-polynomially more compact than the
dense representation (assuming $NP\neq P$)." ]
9, 15, 19 wrong font for closing quotes Buell 6/1/00
15 -8 \Omega(0(g(n))+f(n)) => \Omega(O(g(n))+f(n))
Koegl 1/19/00
19 -5 Khacian => Khachian Koegl 1/19/00
---- CHAP 1: ARITHMETIC -------------------------------------------------------
27 2 of Pascal those who has => those who have Koegl 1/19/00
-4 of Leibniz be repeated => by repeated Koegl 1/19/00
32 -l scalar => componentwise Yap 10/17/00
---- CHAP 2: GCD --------------------------------------------------------------
43 2 DENOMINATOR => DIVISOR Buell 6/1/00
-6 denominator => divisor Buell 6/1/00
45 9 arithmetic => Arithmetic Buell 6/1/00
48 3 lines after
eqn.(2.3) produces => produce Buell 6/1/00
54 4 DENOMINATOR => DIVISOR Buell 6/1/00
63 figure 2.1 length of D should be l-1, not l Stehle 7/9/01
65 -6 +1 => -1 Stehle 7/9/01
65 -5 floor(m'/2)+1 => ceiling(m'/2)-1 Stehle 7/9/01
65 -4 floor(m'/2)+1 => ceiling(m'/2)-1 Stehle 7/9/01
69 Section 2.A.2 The cutoff should be 8, not 4 Stehle 7/9/01
This means: "a<=3 should be "a<=7"
and "a>=4" should be "a>=8".
Changes in 3 places.
73-75 Section 2.A.4 Because of the changes in Section Stehle 7/9/01
2.A.2, we need to rewrite this section.
We will post this in the future (please
contact the author if this is important).
===============================================================================
---- CHAP 3: SUBRESULTANTS ----------------------------------------------------
77 8 alternations => alterations Buell 6/1/00
79 footnote [60] => [63] Buell 6/1/00
81 l. 2, Sect.3.1.3
"either 0<= ord_q(b) <= ord_q(c) or
0<= ord_q(c) <= ord_q(b)."
=> "ord_q(b) <= ord_q(c)" Sharma 2/6/03
82 statement of
lemma 3.4 "\beta = lead(B). Then" =>
"\beta = lead(B), then we have that" Buell 6/1/00
83 -12 multiple GCD => multiple GCDs Buell 6/1/00
85 1 Sylvester => the Sylvester Buell 6/1/00
---- CHAP 4: MODULAR TECHNIQUES -----------------------------------------------
116 l.3 of proof the 2-norm of (X-c)A(X) should be squared
on the left side of the equation Yap 7/1/00
119 7 polynommials => polynomials Buell 6/1/00
123 -10 comment about sparse representation
is confusing Fateman 2/18/00
[FIX: as for page 9, line -9, we
should reword this sentence and clarify.]
-9 we must use now => we must now Fateman 2/18/00
-2 several to => several ways to Fateman 2/18/00
---- CHAP 5: FUNDAMENTAL THEOREM ----------------------------------------------
124 -4 of Hilbert construction => constructions Koegl 1/19/00
-2 of Hilbert may always may => may always Koegl 1/19/00
133 -3 the set V => consider the set V Buell 6/1/00
---- CHAP 6: ROOTS ------------------------------------------------------------
141 4 of Viete thus => Thus Koegl 1/19/00
4 of Viete 1/2 should be raised Yap 2/22/00
-4 of Viete trhe => the Koegl 1/19/00
154 1 is => are Buell 6/1/00
167 8 "=" should be ":=" Fortune 11/30/00
---- CHAP 7: STURM THEORY -----------------------------------------------------
187 -1 Note that ... of PRS. => Note that the
definition of a PRS implies that
$0 = \alpha_i A_{h-1}+Q_h A_h$ for some
$\alpha_h, Q_h$. Yap 3/1/00
192 12 A(X) and B(X) are both => B(X) is Yap 9/27/01
195 Exer.7.2.2 dominats => dominates Fortune 11/30/00
197 2 Omit "A(X) is square free and" Yap 9/27/01
197 9 Wrong bracket Yap 9/27/01
199 7 problem A => problem in Section 7.3.1 Yap 3/1/00
15 problem A => Section 7.3.1 Yap 3/1/00
202 8 polynomial => integer polynomial Fortune 11/30/00
212 lemma 7.14 roots of A =>
roots of A in [\alpha,\beta] Fortune 11/30/00
215 -1 W^{\epsilon\cdot\epsilon} =>
W^{\epsilon\cdot\epsilon'} Fortune 11/30/00
---- CHAP 8: LATTICES ---------------------------------------------------------
219 3 of Minkowski (Leipzig,) => (Leipzig, Koegl 1/19/00
-9 two-dimensions => two dimensions Buell 6/1/00
220 7 delete "or even infinite" Buell 6/1/00
222 line 3 of 8.1.1 Scalar => The scalar Buell 6/1/00
---- CHAP 9: LATTICE REDUCTION ------------------------------------------------
234 5 of Weyl gentlemen => gentleman Koegl 1/19/00
235 -8 LLL algoritmn => LLL algorithm Fateman 2/17/00
-7 Sch\"onlage => Sch\"onhage Fateman 2/17/00
243 12 so => , and so Yap 4/4/00
250 line after
theorem 9.13 involve => involves Buell 6/1/00
---- CHAP 10: LINEAR SYSTEMS --------------------------------------------------
271 -3 r = 1,...,n => r \in \{1,...,n\} Buell 6/1/00
278 -6 relative => relatively Buell 6/1/00
286 3, 4 Bachem and Kannan => Kannan and Bachem Buell 6/1/00
292 11, 14, -5 Bachem and Kannan => Kannan and Bachem Buell 6/1/00
---- CHAP 11 ELIMINATION ------------------------------------------------------
300 1 of Noether years , => years, Koegl 1/19/00
-7 of Artin littler => little Buell 6/1/00
-6 of Artin the => The Koegl 1/19/00
-2 of Artin husbanc's => husband's Koegl 1/19/00
---- CHAP 12 GROEBNER BASES ---------------------------------------------------
370 -4 a => an Buell 6/1/00
371 Ex. 12.1.4 Dixon's => Dickson's [three times] Koegl 1/19/00
383 Ex. 12.4.3 on Sparc a => on a Sparc Koegl 1/19/00
coefficients up => coefficients of up Koegl 1/19/00
Ex. 12.4.4 Show the => Show that Koegl 1/19/00
fm => f_m Koegl 1/19/00
Ideal(f_1,...,fm1-Zp) =>
Ideal(f_1,...,f_m,1-Zp) Koegl 1/19/00
390 Ex. 12.6.7 \overbar{K}_n => \overbar{K}^n Koegl 1/19/00
\overbar{K}[X_1,...,Xn]
=> \overbar{K}[X_1,...,X_n] Koegl 1/19/00
393 10 a => an Buell 6/1/00
---- CHAP 13: BOUNDS ----------------------------------------------------------
398 4 of Mac Lane Neother => Noether Koegl 1/19/00
442 -15 13.A:.1 => 13.A.1 Koegl 1/19/00
445 6 13.A:.2 => 13.A.2 Koegl 1/19/00
---- CHAP 14: CONTINUED FRACTIONS ---------------------------------------------
446 line 1 in quote
of Minkowski investigation, => investigation Buell 6/1/00
452 footnote delete the word "also" Buell 6/1/00
462 line 15 matrix [0 1] => [0 p_i]
[p_i q_i] [1 q_i] Yap 9/26/02
eqn (14.24) matrices [0 1] => [0 p_j]
[p_j q_j] [1 q_j]
(for j=1, 2, i) Yap 9/26/02
463 eqn (14.29) x_i => x_{i+1} V.Sharma
12/24/02
-4 x_i => x_{i+1} V.Sharma
12/24/02
---- REFERENCES ---------------------------------------------------------------
485 [7] Bachem and Kannan => Kannan and Bachem Buell 6/1/00
487 [55] Dixon => Dickson Yap 2/23/00
---- INDEX --------------------------------------------------------------------
---- SYMBOLS ------------------------------------------------------------------
510 -9 (column 2) \sigma should appear above arrow Yap 5/18/00
510 -10 (column 2) \sigma should appear above arrow Yap 5/18/00
===============================================================================
--Chee Yap
File Created: Sep 1999.